TNA010: Computer assignments 3

Namn: Lovisa Svensson

Datum: 2021-12-13

Problem 1

For this problem I have performed a rank-k approximation on a grayscale image, to find out how much an image can be compressed with this method while retaining the image quality.
I thought that k = 100 made the image indistinguishable. k = 60 looks good too at first glance, but has some blurry places. Everything below looks compressed.
The corresponding singular value for k = 100 is 3.3709. The singular values in rank-k approximation represent significant components in the matrix and a higher value -> higher importance.
The degree of compression shows how much of the original data from the image is retained. k = 100 has a compression ratio of 0.14 which means that 14% of the data of the original image is retained, even if the rank-100 approximation is very similar to the original image. (This might be a MATLAB problem though - MATLAB does not display the full size of the image, it is scaled down! k = 100 could be worse than it looks to be here)
clear
clf
 
% Read original image and convert to grayscale
rgb_image = imread("cat.jpg");
gray_image = im2gray(rgb_image);
A = im2double(gray_image);
 
% Show the original image
imshow(A)
title(['Original image']);
 
% Compute the singular values of A
[U, S, V] = svd(A);
figure;
semilogy(diag(S));
title('Singular Values of the Image');
xlabel('Singular Value Index');
ylabel('Singular Value Magnitude');
 
% k values to show
k_values = [10, 30, 60, 100];
 
% Create rank approximation Ak
for i = 1:length(k_values)
k = k_values(i);
 
% Create the rank-k approximation Ak
Ak = U(:, 1:k) * S(1:k, 1:k) * V(:, 1:k)';
 
% Visualize the rank-k approximation
figure;
imshow(Ak);
title(['Rank-', num2str(k), ' Approximation']);
 
% Show the singular value for k
sigma_k = S(k, k);
disp(['The singular value sigma_', num2str(k), ' is: ', num2str(sigma_k)]);
 
% Show the compression ratio for k
compression_ratio = (size(U,1)*k + size(V,1)*k + k) / numel(A);
disp(['The compression ratio for rank-', num2str(k), ' approximation is: ', num2str(compression_ratio)]);
 
end
The singular value sigma_10 is: 33.429
The compression ratio for rank-10 approximation is: 0.014472
The singular value sigma_30 is: 10.3451
The compression ratio for rank-30 approximation is: 0.043417
The singular value sigma_60 is: 5.2111
The compression ratio for rank-60 approximation is: 0.086834
The singular value sigma_100 is: 3.3709
The compression ratio for rank-100 approximation is: 0.14472

Problem 2

A random 20x10-matrix of rank 5.
m = 20;
n = 10;
desired_rank = 5;
 
% Random matrix
A = rand(m, n);
 
% Reduce the rank to the desired value
[U, S, V] = svd(A);
S(desired_rank+1:end, :) = 0;
A = U * S * V';
 
% Display the resulting matrix and its rank
disp(A);
0.2478 0.7712 0.2131 0.1342 0.1843 0.5276 0.6911 0.7841 0.5375 0.1367 0.3046 0.8633 0.1591 0.0584 0.8715 -0.0818 0.1790 0.2621 0.9715 0.4996 0.4528 1.0695 0.4589 0.9453 0.6789 0.6861 0.5594 0.9436 0.2514 0.7789 0.8614 0.1838 0.5174 0.7555 0.4555 0.9841 0.2968 0.0436 0.3105 0.7882 0.4569 0.6234 0.6790 0.2862 0.6938 0.3420 0.5736 0.5292 0.7913 0.3419 0.4739 0.6731 0.4890 0.6152 0.7083 0.4252 0.3484 0.4627 0.4509 0.6332 0.5370 0.5745 0.3734 0.2126 0.7382 0.2947 0.2852 0.1646 0.8658 0.5330 0.1092 0.3430 0.9157 0.4221 0.4899 0.0856 0.5611 0.7134 0.1994 0.0206 0.5519 0.3275 0.7807 0.9226 0.5419 0.6804 0.4036 0.4655 0.0337 0.6141 0.7215 0.2919 0.4983 0.1648 0.2505 0.8958 0.6610 0.2761 0.7712 0.3012 0.1728 0.8938 0.1625 0.6956 0.4647 0.3565 0.3177 0.7565 0.0481 0.5618 0.5395 0.3779 0.8119 0.2563 0.6373 0.4106 0.5787 0.3802 0.7853 0.2810 0.3893 0.7280 0.4400 0.1308 0.4496 0.4590 0.6791 0.6528 0.7949 0.2227 0.5944 0.3414 0.9040 0.6036 0.5738 0.6404 0.6015 0.4923 0.4467 0.4147 0.5427 0.8183 0.2207 1.0076 0.5308 0.8072 0.2948 0.5824 0.0372 0.9240 0.5279 0.3207 0.8245 0.7695 0.5846 0.5709 0.4353 0.4453 0.1965 0.5187 0.4709 0.4318 0.5305 0.3180 0.0120 0.9382 0.8667 0.7509 0.3762 0.1086 0.6177 0.2617 0.3080 0.1726 0.2875 0.6850 0.4024 0.1025 0.6370 0.3750 0.3268 0.3476 0.6276 0.1511 0.6130 0.0980 0.3707 0.2824 0.6543 0.2044 0.3427 0.6987 0.0662 0.2585 0.1371 0.6657 0.5454 0.6131 0.4042 0.3104
 
% The rank is:
disp(['The rank is: ', num2str(rank(A))]);
The rank is: 5

Problem 3

Solving the minimum norm least squares problem for a rank 5 matrix using SVD.
clear
clf
 
m = 20;
n = 10;
k = 5;
 
A = rand(m, n);
[U, S, V] = svd(A);
 
Ak = U(:, 1:k) * S(1:k, 1:k) * V(:, 1:k)';
 
e = ones(n, 1);
b = Ak*e;
 
x = pinv(Ak)*b
x = 10×1
1.0529 1.0439 1.1666 0.9049 0.8899 1.1974 1.1090 0.6958 0.8220 0.8726
% a) Check if x* is equal to e
disp('Is x* approximately equal to e?');
Is x* approximately equal to e?
disp(x-e);
0.0529 0.0439 0.1666 -0.0951 -0.1101 0.1974 0.1090 -0.3042 -0.1780 -0.1274
It is approximately equal, as x is a vector with values around 1. (x is the acutal least norm)
% b) Compare the norms of x* and e
disp(norm(x)); % Norm of x
3.1233
disp(norm(e)); % Norm of e
3.1623
The norm of x is slightly smaller than the norm of e, as expected if x should be smaller than e.
% c) Check the residual norms
disp(norm(b - Ak*e));
0
disp(norm(b - Ak*x));
1.3076e-14
It is as good as 0. (Can't be zero if all elements are not zero)
% d) Check the orthogonality condition
disp(Ak * (e - x)); % A*y
1.0e-14 * 0.2387 0.1795 0.3841 0.2776 0.1568 0.1041 0.4018 0.3109 0.4413 0.3553 0.4996 0.4441 0.2373 0.3275 0.2706 0.1801 0.2456 0.0583 0.1270 -0.0111
y is the difference between the basic solution e and the least norm x. So y contains values that are not seen in A.